package ljl.alg.wangzheng_camp.round1.array_and_list;

import commons.ListNode;

import java.util.LinkedList;

public class _234_palindrome_list {
    
    /**
     * 这个题也是有很多解法
     * 1. 栈？
     * 2. 找到中点，翻转链表，再比较？
     * 3. 递归？
     *
     * 递归有点意思！我应该不会写，不过这是个学习的好机会
     *
     * 都写写吧，看你是不是真会
     * */
    public boolean isPalindrome3(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = reverse(slow);
        // slow 和 p 比较即可
        ListNode p = head;
        while (slow != null) {
            if (slow.val != p.val) return false;
            slow = slow.next;
            p = p.next;
        }
        return true;
    }
    ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode n = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return n;
    }
    
    public boolean isPalindrome2(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode p = head;
        int count = 0;
        while (p != null) {
            count++;
            stack.push(p);
            p = p.next;
        }
        
        p = head;
        for (int i = 0; i < count / 2; i++) {
            if (p.val != stack.pop().val) return false;
            p = p.next;
        }
        return true;
    }
    
    /**
     * 谁能教教我递归咋写？
     * 优雅！
     * 就是慢
     * */
    ListNode head;
    public boolean isPalindrome(ListNode head) {
        this.head = head;
        return check(head);
    }
    boolean check(ListNode node) {
        if (node != null) {
            if (!check(node.next) || node.val != head.val) return false;
            head = head.next;
        }
        return true;
    }
    
    
    /*
    * 还有个解法，拷贝到数组里，再双指针
    * 没什么意思不写了
    * */
    
}
